class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
}
class QueueNode {
    constructor(pt, dist) {
        this.pt = pt;
        this.dist = dist;
    }
}

function BFS(maze, src, dest) {
    const ROW = maze.length;
    const COL = maze[0].length;
    const moves = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    var isValid = (row, col) => (row >= 0) && (row < ROW) && (col >= 0) && (col < COL);
    if (maze[src.x][src.y] != 1 || maze[dest.x][dest.y] != 1) return -1;
    var visited = Array.from({ length: ROW }, (_, i) => Array.from({ length: COL }, (_, j) => false));
    visited[src.x][src.y] = true;
    var q = [];
    var s = new QueueNode(src, 0);
    q.push(s);
    while (q.length) {
        curr = q.shift();
        if (curr.pt.x === dest.x && curr.pt.y === dest.y) return curr.dist;
        for (mov of moves) {
            var row = curr.pt.x + mov[0];
            var col = curr.pt.y + mov[1];
            if (isValid(row, col) && maze[row][col] === 1 && !visited[row][col]) {
                visited[row][col] = true;
                Adjcell = new QueueNode(new Point(row, col), curr.dist + 1);
                q.push(Adjcell);
            }

        }
    }
    return -1;
}

function test() {
    mat = [[1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
    [1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
    [1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 1, 1, 0, 1, 1, 1, 0, 1, 0],
    [1, 0, 1, 1, 1, 1, 0, 1, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
    [1, 1, 0, 0, 0, 0, 1, 0, 0, 1]]
    source = new Point(0, 0)
    dest = new Point(3, 4)

    dist = BFS(mat, source, dest);
    console.log(dist)
}
test()